
#include "lnBinTree.h"


PLNBinTree createEmptyBinTree()
{
/*
    PLNBinTree t = (PLNBinTree) malloc(sizeof(struct BinTreeNode));
    
    if (t != NULL)
    {
        t->info = 'A';
        t->lchild = NULL;
        t->rchild = NULL;
    }
*/
    
    return NULL;
}

PLNBinTree constructBinTree(PBinTreeNode root, PLNBinTree left, PLNBinTree right)
{
    if (root == NULL)
    {
        return NULL;
    }
    
    root->lchild = duplicateBinTree(left);
    root->rchild = duplicateBinTree(right);
    
    return root;
}

PLNBinTree duplicateBinTree(PLNBinTree t)
{
    PLNBinTree q = NULL;
    
    if (t != NULL)
    {
        q = (PBinTreeNode) malloc(sizeof(struct BinTreeNode));
        if (q != NULL)
        {
            q->info = t->info;
            if (t->lchild != NULL)
            {
                q->lchild = duplicateBinTree(leftChild(root(t), t));
            }
            else
            {
                q->lchild = NULL;
            }
            if (t->rchild != NULL)
            {
                q->rchild = duplicateBinTree(rightChild(root(t), t));
            }
            else
            {
                q->rchild = NULL;
            }
        }
    }
    
    return q;
}

int addChildBinTree(PLNBinTree *t, PBinTreeNode c, ELEMTYPE x, int flag)
{
    PBinTreeNode newNode;
    /**
     * if t is an empty binary tree, then create a new node as the root node
     * and ignore the flag parameter
     *
     */
    if (isNULL(*t))
    {
        newNode = (PBinTreeNode) malloc(sizeof(struct BinTreeNode));
        if (newNode != NULL)
        {
            newNode->info = x;
            newNode->lchild = NULL;
            newNode->rchild = NULL;
            *t = newNode;
            return 1;
        }
        return -1;
    }

    if (c != NULL)
    {
        newNode = (PBinTreeNode) malloc(sizeof(struct BinTreeNode));
        if (newNode != NULL)
        {
            newNode->info = x;
            newNode->lchild = NULL;
            newNode->rchild = NULL;
            if (flag == 1)
            {
                newNode->lchild = c->lchild;
                c->lchild = newNode;
            }
            else
            {
                newNode->rchild = c->rchild;
                c->rchild = newNode;
            }
            
            return 1;
        }
        return -1;
    }
    return 0;
}

int deleteChildBinTree(PLNBinTree t, PBinTreeNode c, int flag)
{
    PBinTreeNode l, r, q, p, lleaf;
    if (isNULL(t))
    {
        return -1;
    }
    
    if (c == NULL)
    {
        return 0;
    }
    
    l = c->lchild;
    r = c->rchild;

    if (flag == 1)
    {
        if (l == NULL)
        {
            return 1;
        }
        
        q = l->lchild;
        p = l->rchild;
        if (p != NULL)
        {
            lleaf = l;
            while (lleaf->lchild != NULL)
            {
                lleaf = lleaf->lchild;
            }
            lleaf->lchild = p;
        }
        free(l);
        c->lchild = q;
        return 1;
    }
    else
    {
        if (r == NULL)
        {
            return 1;
        }
        q = r->lchild;
        p = r->rchild;
        
        if (p != NULL)
        {
            lleaf = r;
            while (lleaf->lchild != NULL)
            {
                lleaf = lleaf->lchild;
            }
            lleaf->lchild = p;
        }
        free(r);
        c->rchild = q;
        return 1;
    }
    return 0;
}

PBinTreeNode locateChildBinTree(PLNBinTree t, ELEMTYPE x)
{
    PBinTreeNode p, c;
    PLQueue queue;

    queue = createQueue();

    if (isNULL(t))
    {
        return;
    }

    if (queue != NULL)
    {
        p = t;
        enqueue(queue, p);
        while (!isEmpty(queue))
        {
            frontQueue(queue, &p);
            if (p->info == x)
            {
                break;
            }

            if ((c = leftChild(t, p)) != NULL)
            {
                enqueue(queue, c);
            }

            if ((c = rightChild(t, p)) != NULL)
            {
                enqueue(queue, c);
            }

            p = NULL;
            dequeue(queue);
        }
        destroyQueue(&queue);
        return p;
    }

    return NULL;
}

int isNULL(PLNBinTree t)
{
    return (t == NULL);
}

PBinTreeNode root(PLNBinTree t)
{
    if (isNULL(t))
    {
        return NULL;
    }
    else
    {
        return t;
    }
}

PBinTreeNode parent(PLNBinTree t, PBinTreeNode c)
{
    PBinTreeNode p, q;
    PLQueue queue;

    if (isNULL(t))
    { 
        return NULL;
    }
    
    if (c == NULL)
    {
        return NULL;
    }
    
    queue = createQueue();

    if (queue != NULL)
    {
        p = t;

        if (p == c)
        {
            return NULL;
        }

        enqueue(queue, p);

        while (!isEmpty(queue))
        {
            frontQueue(queue, &p);
            if (p->lchild == c || p->rchild == c)
            {
                break;
            }

            if ((q = leftChild(t, p)) != NULL)
            {
                enqueue(queue, q);
            }

            if ((q = rightChild(t, p)) != NULL)
            {
                enqueue(queue, q);
            }

            p = NULL;
            dequeue(queue);
        }

        destroyQueue(&queue);
        return p;
    }

    return NULL;
}

PBinTreeNode leftChild(PLNBinTree t, PBinTreeNode p)
{
    if (p != NULL)
    {
        return p->lchild;
    }

    return NULL;
}

PBinTreeNode rightChild(PLNBinTree t, PBinTreeNode p)
{
    if (p != NULL)
    {
        return p->rchild;
    }

    return NULL;
}

void preOrder(PLNBinTree t);
void inOrder(PLNBinTree t);
void postOrder(PLNBinTree t);

void levelOrder(PLNBinTree t, int flag)
{
    PBinTreeNode p, c;
    PLQueue queue;

    queue = createQueue();

    if (isNULL(t))
    {
        return;
    }

    if (queue != NULL)
    {
        p = t;
        enqueue(queue, p);
        while (!isEmpty(queue))
        {
            frontQueue(queue, &p);
            if (flag != 1)
            {
                visit(t, p);
            }
            else
            {
                printf("CURRENT NODE : %c\n", p->info);
                printf("CURRENT ADDRESS : %u\n", p);
                printf("LEFT CHILD ADDRESS  : %u\n", p->lchild);
                printf("RIGHT CHILD ADDRESS : %u\n\n", p->rchild);
            }

            if ((c = leftChild(t, p)) != NULL)
            {
                enqueue(queue, c);
            }

            if ((c = rightChild(t, p)) != NULL)
            {
                enqueue(queue, c);
            }

            dequeue(queue);
        }
        destroyQueue(&queue);
    }
}

int leaf(PLNBinTree t)
{
	if (isNULL(t))
	{
		return 0;
	}
	if (t->lchild == NULL && t->rchild == NULL)
	{
		return 1;
	}

	return leaf(leftChild(root(t), t)) + leaf(rightChild(root(t), t));
}

int visit(PLNBinTree t, PBinTreeNode p)
{
    if (isNULL(t))
    {
        return -1;
    }
    
    printf("NODE : %c\n", p->info);
    return 1;
}

/**
 * print the binary tree in a level order manner.
 *
 */
int print(PLNBinTree t)
{

   if (isNULL(t))  
   {
       return 0;
   }
   
   levelOrder(t, 1);
   return 1;
}

int destroyBinTree(PLNBinTree t)
{
    if (!isNULL(t))
    {
        destroyBinTree(t->lchild);
        t->lchild = NULL;
        destroyBinTree(t->rchild);
        t->rchild = NULL;
        free(t);
        t = NULL;
        return 1;
    }
    return 0;
}
